package _3sort.src;
//堆排序
//时间复杂度：O(nlogn)，空间复杂度：O(1)
public class _6HeapSort {
    public static void main(String[] args) {
        int[] nums = {2, 4, 7, 32, 7, 4, 7};
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
        System.out.println();
        System.out.println("========================");
        HeadSort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
        System.out.println();
        System.out.println("（0-1）/2 = "+(0-1)/2);
    }

    public static void HeadSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;//代表无需排序
        }
        for (int i = 0; i < nums.length; i++) {
            heapInsert(nums, i);
        }
        int size = nums.length;
        swap(nums, 0, --size);//将最大的一个值（树根）和最后的那个值进行交换，也就是将最大的值给放在了数组最后那个地方
        while (size > 0) {//O(n)
            heapity(nums, 0, size);//O(logn)
            swap(nums, 0, --size);
        }

    }

    //用于交换两个值
    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    //用于构成堆二叉树
    public static void heapInsert(int[] nums, int index) {
        while (nums[index] > nums[(index - 1) / 2]) {
            swap(nums, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     *
     * @param nums：要进行操作的数组
     * @param index：传入的数字索引
     * @param size：数组的大小
     */
    public static void heapity(int[] nums, int index, int size) {
        //获取输入索引的子左孩子索引，用于后续比较大小和交换位置
        int l = index * 2 + 1;
        while (l < size) {
            //要先判断是否有右孩子，然后才能进行左右孩子的大小的比较
            int best = l + 1 < size && nums[l] < nums[l + 1] ? l+1 : l ;//返回书中较大的那个索引
            //判断父和子谁大谁小？
            best = nums[best] > nums[index] ? best : index;
            if (best == index) {
                break;
            }
            swap(nums, best, index);
            index = best;
            l = index * 2 + 1;
        }
    }
}
